package pers.qianyu.month_202012.date_20201214;

import java.util.*;

/**
 * 2. 01背包问题
 * https://www.acwing.com/problem/content/description/2/
 *
 * @author mizzle rain
 * @date 2020-12-14 18:02
 */
public class Bag01 {
    // 重量
    private int[] heights;
    // 价值
    private int[] values;
    private int cap;
    private int count;

    public void input() {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        count = Integer.parseInt(s[0]);
        cap = Integer.parseInt(s[1]);
        heights = new int[count];
        values = new int[count];
        for (int i = 0; i < count; i++) {
            heights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
    }

    public int solve() {
        int[][] dp = new int[count + 1][cap + 1];
        for (int i = 1; i < count + 1; i++) {
            for (int j = 1; j < cap + 1; j++) {
                if (j < heights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i - 1][j - heights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[count][cap];
    }

    /**
     * 状态压缩
     */
    public int solve2() {
        int[] dp = new int[cap + 1];
        for (int i = 1; i < count + 1; i++) {
            for (int j = cap; j > 0; j--) {
                if (j - heights[i - 1] >= 0) {
                    dp[j] = Math.max(dp[j],
                            dp[j - heights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        Bag01 bag = new Bag01();
        bag.input();
        System.out.println(bag.solve());
    }

    @Override
    public String toString() {
        return "Bag01{" +
                "heights=" + Arrays.toString(heights) +
                ", values=" + Arrays.toString(values) +
                ", cap=" + cap +
                ", count=" + count +
                '}';
    }
}
